In modern satellite communications networks, often consisting of dozens of satellites and numerous surface facilities, the process of determining which links to use in communicating between one point in the network and another can be extremely complex, time-consuming and error prone. In addition to such considerations as minimizing distance or the number of links, other factors such as location and conditions that may impact the quality of a given link can make one link more or less costly than another. Given such factors, determining the optimal combination of links to use in a specific situation can require hours of complex calculations with a significant possibility of error.
What is "optimal" will depend upon priorities and factors important to a given user or situation, but includes such criteria as minimizing the number of separate links or avoiding links that are undesirable due to distance, location (e.g. outside certain latitudes), interference factors, loading, limited availability, lack of reliability and other negative characteristics.
A satellite communications system that utilizes satellites in geosynchronous orbit is generally a static system, since the spacecraft do not change position appreciably relative to relay stations on the ground beneath them. Geosynchronous satellites, however, operate in very high altitudes on the order of 22,000 statue miles. The propagation delays inherent in conveying signals over a nearly 50,000 mile round-trip are not acceptable for many communication environments. Low Earth orbit systems are seen to be essentially static where one satellite merely hands off a communication to another satellite which moves into its place, covering the same cells on the Earth's surface as its predecessor-in-orbit.
A path between any two arbitrary nodes in the network is a sequence of nodes from the originating (source) node to the terminating (destination) node. In order to select a "best" path, some figure of merit for any candidate path is derived. The figure of merit consists of the additive "costs" of each of the links between nodes derived from the connectivity matrix. The link costs may include the additive "costs" associated with the nodes. Thus the cost of a path is just the sum of the link costs between adjacent nodes in the path sequence.
Regardless of the algorithm used to transform the network nodal connectivity to the "shortest path" between two nodes, (e.g., Floyd's Algorithm or Dijkstra's Algorithm, both provided in Introduction to Algorithms by Thomas Cormen, Charles Leiserson and Ronald Rivest, .COPYRGT. 1990, chapter 25 for Dijkstra's Algorithm and chapter 26 for Floyd's Algorithm, therein referred to as the Floyd-Warshall Algorithm, which is the alternative nomenclature for Floyd's Algorithm), the cost of such a path is obtainable by taking the sum of the link costs, perhaps including some additive nodal cost, either by using Floyd's Algorithm or Dijkstra's Algorithm to make the required determination. As long as there is a single link cost factor used to determine the cost for the logical or physical links between two nodes, the approach to determining the shortest path value is straightforward.
The situation is not as clear cut when there are two or more independent cost factors used to determine an aggregate cost for a path to be used in evaluating the best or shortest path. It will be understood that when multiple costs are considered for evaluating a best or shortest path, the various cost considerations lead to different "shortest path" conclusions. For example, if hop count, i.e., the number of nodes traversed by a packet from source to destination node, is an overwhelming concern, one path within a network may be the shortest path. Alternatively, if delay is the major factor, i.e., the time it takes for a packet to travel from the source to the destination node, then another path within the network may be the best path. Still different conclusions may be reached if other factors, such as monetary cost, are taken into consideration.
When single cost functions are used as a means of obtaining figures of merit for various paths within the network, the concept of adding the costs of each link in the path, as discussed above, is the natural way to obtain the result. Known routing algorithms assume that costs add as the path is traversed. Common cost functions, used in path selection (e.g., "delay", "cost of transmission line facility", "hop count"), are additive. Individually, they are immediately adaptable to standard path-cost-determination algorithms. However, there are other cost-factors, (e.g., "percent available bandwidth", "ability to handle a specific protocol", "ability to handle a certain packet type") which are major determiners of path selection, but which are not additive. These types of cost factors cannot be treated by usual connectivity matrix based methods. The reason is that arithmetic addition is too limiting to describe the actions of many cost factors.
Therefore, a method for handling multi-cost factors in determining the relative costs of paths within a network is needed. Additionally, this method for handling multi-cost factors should also be capable of considering non-additive cost factors in the relative costs of paths determination.
The methods and apparatus disclosed in U.S. Pat. No. 5,740,164 to Liron, comprises software and hardware which manage satellite communication links between the origin and destination of telephone calls which convey voice, data, or video information. The methods of this invention select the best series of connections from a terrestrial gateway or terminal up through a satellite constellation and back down to Earth. The constellation operates in low Earth orbit, and provides continuous worldwide service. The pathway that is selected for a particular call is adaptive and able to change rapidly in response to the constantly changing geometry of the low Earth orbit constellation. Based upon inputs from the position determination algorithms that define the length of each link in the system, algorithms are provided to determine the optimal route for each transmission from each satellite and also establish the most efficient distribution pattern of traffic throughout the system.
In U.S. Pat. No. 4,905,233, issued Feb. 27, 1990, Cain et al. disclose a mechanism for establishing at least one transmission route between a source node and a destination node in a communications network. Transmission characteristics of each of the transmission paths among the nodes of the network are monitored so as to derive a plurality of path metrics representative of the ability of the network to transmit communication signals. Feasible transmission routes from source node to destination node are selected where the sum of path metrics from neighboring nodes to the destination node is less than the path metric of a transmission path, the end nodes of which correspond to the source and destination nodes. Communication signals are then transmitted from the source node to the destination node over the selected feasible transmission routes. Typical link metrics are presented, which include as terms normalized propagation plus processing delay, and expected transmission delay including queuing delay. Cain et al. do not describe a specific method of packet switching and routing in a low Earth orbit satellite communication system in which the metrics or algorithms are implemented to provide synchronous circuit switched communications services with uniform end-to-end transmission delays. While Cain et al. indicate that their system updates link metrics periodically at each node, they do not appear to reveal an adaptive, dynamic, distributed routing system which continuously runs an adaptive routing algorithm to pre-calculate the optimal route for each packet, one step at a time, at each satellite. Cain's routing procedure is autonomous in that each node determines a set of routing tables with no inputs from other nodes (Cain et al. at col. 8, line 28-29). According to U.S. Pat. No. 5,754,543 to Seid, connectivity matrix-based multi-cost routing includes defining a generally additive operator which is able to add traditionally (arithmetic) additive cost factors and which takes into account cost factors which are not additive, the generally additive operator being defined such that distributive and commutative properties are applicable, and wherein the generally additive operator is applicable to connectivity matrix-based factors for determining the relative costs of paths within a network, particularly with respect to multi-cost factors.
While there exist processes such as Floyd's Algorithm for finding the least expensive path between all vertices in a graph, or Dijkstra's Algorithm for finding the lowest cost path between a single starting vertex and all of the other vertices in a graph, there is no procedure specifically designed to take account of the complexities of a modern telecommunications network, especially a satellite network subject to constant changes in its geometries and other factors that affect the availability and quality of communications links.
In view of the complexities of modern communication systems, what is needed is an automated procedure specifically designed to determine the optimal path among the objects of a satellite communications chain. Such a procedure, employing a suitable least cost path algorithm as one of its components, would address the dynamically changing situation in which the communications task is being carried out. The procedure would provide quick and reliable numerical data and graphic displays to assist the user or controller in identifying the optimal path, preferably utilizing an existing computer program for satellite system analysis.